package algorithm.dynamicprogramming;


/**
 * 01背包问题
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-04-06
 */
public class Bag {

    public static void main(String[] args){
        // 物品价格，第0个物品价格为0， 单纯为了逻辑清楚,这样index = 物品编号
        int[] v = {0, 1500, 3000, 2000};
        // 物品需要的容量，第0个物品重量为0
        int[] w = {0, 1, 4, 3};
        // 背包最大可以使用的容量
        int capacity = 4;
        System.out.println("最多可在背包中存放价值为：" + maxValue(v, w, capacity) + "的物品");
    }

    public static int maxValue(int[] v, int[] w, int capacity){
        // value[i][j]表示只考虑前i个物品，在能用j 容量的情况下最多可以放价值为value[i][j]的东西
        int[][] value = new int[v.length][capacity + 1];
        // 用来记录存放了哪些物品
        int[][] g = new int[v.length][capacity + 1];

        // 从第1个物品开始，依次推导
        for(int i = 1; i < v.length; i++){
            // 从最大容量是1到背包最大值，依次推导
            for(int j = 1; j <= capacity; j++) {
                if (w[i] > j) {
                    // 如果新加入考虑的物品的重量已经超过了背包最大容量，则不用考虑，依然使用只考虑它之前那些物品的方案
                    value[i][j] = value[i - 1][j];
                } else {
                    // value[i][j] = Math.max(value[i - 1][j], v[i] + value[i - 1][j - w[i]]);
                    // 当value[i - 1][j] < v[i] + value[i - 1][j - w[i]] 时，也就是新策略比旧策略好时，记录新策略用到的物品
                    // 从之前的记录中找到没加入新物品时，在容量为最大容量 - 新物品重量 时使用的策略 + 新物品
                    if(value[i - 1][j] > v[i] + value[i - 1][j - w[i]]){
                        value[i][j] = value[i - 1][j];
                    } else{
                        value[i][j] = v[i] + value[i - 1][j - w[i]];
                        // 记录在容量为 j， 考虑前 i 个物品时，最优策略中物品i被放入了。
                        g[i][j] = 1;
                    }
                }
            }
        }
        for(int i = 0; i < value.length; i++){
            for(int j =0; j < value[i].length; j++){
                System.out.print(value[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("-------------------------------------------------");
        for(int i = 0; i < g.length; i++){
            for(int j =0; j < g[i].length; j++){
                System.out.print(g[i][j] + " ");
            }
            System.out.println();
        }
        //显示物品加入情况的表
        //i和 j 是是背包可用容量为 j 时 ，最优解是否用到了物品 i， 但是因为我们考虑的时候中间每次都会放入数组，所以需要从后往前遍历;
        //当发现最后结果中有某一个物品被放入时，就把最大可用容量变成 当前最大可用容量 - 被放入物品的重量，然后继续继续往前寻找
//        0 0 0 0 0
//        0 1 1 1 1
//        0 0 0 0 1
//        0 0 0 1 1
        //最开始先看最后一排，发现 g[4][3] 是 1，说明最大背包容量为 4 时，最终策略中放入了物品3
        //这时候可以知道，最优策略中有物品3，且除了物品3，剩余空间可能也是使用了最优策略。
        //除去物品3，背包剩余容量为1，从g[4-3][2] 开始继续往前找。 g[1][2] 是0， 说明剩余空间的最优策略中没有物品2，继续往前找 g[1][1]
        //g[1][1] = 1 说明拿掉物品3后，背包剩余容量为1时，最优策略中有物品1。
        //除去物品1， 背包剩余容量为0， 继续往前寻找， g[0][0] = 0, 此时走到了尽头，说明没有其他物品被放入。.

        int i = g.length - 1;
        int j = g[0].length - 1;
        while(i > 0 && j > 0){
            if(g[i][j] == 1){
                System.out.println("第" + i + "个物品被放入了背包");
                j = j - w[i];
            }
            i--;
        }

        return value[v.length - 1][capacity];
    }

}